package algorithm.t202111;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/22 10:36
 * @description :7道
 * 开题报告，论文答辩，忙碌的生活就要开始了，开始了。节气：小雪，收拾收拾去跑步，毕竟身体是革命的本钱。
 * persevere to last
 * 2021.11.22
 * 李红磊
 * 2021年11月22日19:53:13
 */
public class t20211122 {

    //剑指55.二叉树的深度1
    public int maxDepth(TreeNode root) {
        return 0;
    }

    //剑指55.平衡二叉树2
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.right) && isBalanced(root.left);
    }

    private int depth(TreeNode cur) {
        if (cur == null) return 0;
        return Math.max(depth(cur.left), depth(cur.right)) + 1;
    }

    //剑指64.求1+2+...+n
    int res = 0;

    public int sumNums(int n) {
        boolean tem = n > 1 && sumNums(n - 1) > 0;
        res += n;
        return res;
    }

    //剑指68.二叉搜索树的最近公共祖先1
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (root.val < p.val && root.val < q.val) root = root.right;
            else if (root.val > p.val && root.val > q.val) root = root.left;
            else break;
        }
        return root;
    }

    //剑指68.二叉搜索树的最近公共祖先2
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root.val == p.val || root.val == q.val) return root;
        TreeNode left = lowestCommonAncestor2(root.left, p, q);
        TreeNode right = lowestCommonAncestor2(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }

    //剑指07.重建二叉树
    int[] preorder;//标记前序遍历
    HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //三个索引分别为
        //当前根的的索引
        //递归树的左边界，即数组左边界
        //递归树的右边界，即数组右边界
        return recursive(0, 0, inorder.length - 1);
    }

    private TreeNode recursive(int pre_root, int in_left, int in_right) {
        if (in_left > in_right) return null;//相等的话就位自己
        //构建根节点
        TreeNode root = new TreeNode(preorder[pre_root]);
        //获取在中序遍历中【根节点】的下标索引，用于来获取  左子树的数量
        int idx = map.get(preorder[pre_root]);
        //左子树根节点索引为先序中索引+1（在前序中
        //递归左子树的左边界为中序的in_left
        //递归左子树的右边界为idx-1
        root.left = recursive(pre_root + 1, in_left, idx - 1);

        //右子树的根节点索引为【根节点】索引+左子树数量+1
        //递归右子树的左边界为idx+1
        //递归右子树的右边界为中序的In_right
        root.right = recursive(pre_root + (idx - in_left) + 1, idx + 1, in_right);
        return root;
    }


    //剑指16.数值的整数次方
    public double myPow(double x, int n) {
        if (x == 0) return 0;
        double res = 1.0;
        long b = n;

        while (b < 0) {
            x = 1 / x;
            b = -b;
        }

        while (b > 0) {
            if ((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println( Math.pow(2, -1));
        t20211122 t20211122 = new t20211122();
        System.out.println("测试" + t20211122.myPow(2, -2));

    }

}

//384.打乱数组
class Solution3 {

    private int[] arr, original;
    Random random;

    public Solution3(int[] nums) {
        arr = nums;
        original = arr.clone();
        random = new Random();
    }

    public int[] reset() {
        arr = original;
        original = original.clone();
        return arr;
    }

    private int randRange(int min, int max) {
        return random.nextInt(max - min) + min;
    }

    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public int[] shuffle() {
        int len = arr.length;

        for (int i = 0; i < len; i++) {
            swap(i, randRange(i, len));
        }

        return arr;
    }


}